public class BinaryTree {
    public static class BTNode {
        public char val;
        public BTNode left;
        public BTNode right;

        public BTNode(char val) {
            this.val = val;
        }
    }
    //创建二叉树
    /*public BTNode createBinaryTree() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
        return node1;
    }*/

    //创建二叉树
    public int i = 0;
    public BTNode createBinaryTree(String str) {
        BTNode root = null;
        if (str.charAt(i) != '#') {
            root = new BTNode(str.charAt(i));
            i++;
            root.left = createBinaryTree(str);
            root.right = createBinaryTree(str);
        } else {
            i++;
        }
        return root;
    }

    // 前序遍历
    void preOrder(BTNode root) {
        if (root == null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(BTNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(BTNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    //求节点个数
    //遍历思路
    public static int nodeSize = 0;
    public void size(BTNode root) {
        if (root == null) return;
        nodeSize++;
        size(root.left);
        size(root.right);
    }

    //子问题思路
    public int size2(BTNode root) {
        if (root == null) return 0;
        return size2(root.left) + size2(root.right) + 1;
    }

    //求叶子节点的个数
    //遍历思路
    public static int leafNodeCount = 0;
    public void getLeafNodeCount(BTNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            leafNodeCount++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }

    //子问题思路
    public int getLeafNodeCount2(BTNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

    //求第K层节点的个数
    //子问题思路
    public int getLevelNodeCount(BTNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        return getLevelNodeCount(root.left, k-1) + getLevelNodeCount(root.right, k-1);
    }

    // 获取二叉树的高度
    public int getHeight(BTNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 检测值为value的元素是否存在
    //前序遍历的方法
    public BTNode find(BTNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        find(root.left ,val);
        find(root.right ,val);
        return null;
    }


    //反转二叉树
    public BTNode invertTree(BTNode root) {

        if (root == null) return null;

        BTNode tmp = root.left;

        root.left = root.right;

        root.right = tmp;

        invertTree(root.left);

        invertTree(root.right);

        return root;
    }

    public boolean isSameTree(BTNode p, BTNode q) {
        //结构不相同的情况
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        //结构相同但为空
        if (p == null && q == null) {
            return true;
        }
        //结构相同值不同
        if (p.val != q.val) {
            return false;
        }
        //值相同
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
